import java.util.Scanner;

public class test {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int[] w= new int[5];
        System.out.println("请输入重量：");
        for (int i = 0; i < 5; i++) {
            w[i]=sc.nextInt();
        }
        int[] v= new int[5];
        System.out.println("请输入价值：");
        for (int i = 0; i < 5; i++) {
            v[i]=sc.nextInt();
        }
        System.out.println(bag(w,v,10));
    }
    public static int bag(int[] w,int[] v,int n) {   //w[]是重量 v[]是价值  n 是背包容量
        int [][] dp=new int[w.length+1][n+1];    //初始值dp[0][0至n]和dp[0至n][0]初始值为0，因为java数组初始值全为0，所以不用特殊定义
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("--------------");
        for (int i=1;i<=w.length;i++) {
            for (int j=1;j<=n;j++) {
                if(w[i-1]>j) {    //由于dp数组i要从1开始，所以w数组要减一，避免数组越界（dp[1]的时候w[0]）
                    dp[i][j]=dp[i-1][j];
                }
                else
                    dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[w.length][n];
    }
}
